Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?


In [5]:
let createNewRow lst = [ 1UL ] @ lst @ [ 1UL ]

let rec contracting (row:uint64[]) =
    if row.Length = 1 then row.[0]
    else
        [0..(row.Length-2)]
        |> List.map (fun i -> row.[i] + row.[i+1])
        |> List.toArray
        |> contracting 
        
        
let rec expanding max (row:uint64[]) = 
    if row.Length > max then contracting row
    else
        [0..(row.Length-2)]
        |> List.map (fun i -> row.[i] + row.[i+1])
        |> createNewRow
        |> List.toArray
        |> expanding max
        
expanding 3 [| |]


Out[5]:
20UL

In [ ]: